// 45. 跳跃游戏 II
/**
 * @param {number[]} nums
 * @return {number}
 */

// 反向贪心
var jump = function (nums) {
    let position = nums.length - 1
    let steps = 0
    while (position) {
        for (let i = 0; i < position; i++) {
            if (i + nums[i] >= position) {
                position = i
                steps++
                break
            }
        }
    }

    return steps
};

// 正向贪心
/* 
    每次在上次能跳到的范围(end) 内选择一个能跳的最远的位置
    也就是能跳到maxPosition位置的点作为下一次的起跳点
*/
var jump = function (nums) {
    let len = nums.length
    let end = 0 //上次跳跃可达范围右边界(下次的最右起跳点)
    let maxPosition = 0 //目前能跳到的最远位置
    let steps = 0 //跳跃的次数
    for (let i = 0; i < len - 1; i++) {
        maxPosition = Math.max(maxPosition, i + nums[i])
        // 到达上次能跳跃的右边界了
        if (i === end) {
            end = maxPosition //目前能跳跃的最远位置成了下次起跳位置的右边界
            steps++
        }
    }

    return steps
}
var jump = function (nums) {
    var len = nums.length
    var dp = [0] //dp[i] 表示跳到i的最小次数
    for (var i = 1; i < len; i++) {
        dp[i] = Number.MAX_VALUE
        for (var j = 0; j < i; j++) {
            if (j + nums[j] >= i) {
                dp[i] = Math.min(dp[i], dp[j] + 1)
            }
        }
    }
    return dp[len - 1]
}
const result = jump([2, 3, 1, 1, 4])

console.log("result :>>", result);